package T11_20;

import java.util.Deque;
import java.util.LinkedList;

public class T11 {
    public int[] maxSlidingWindow(int[] nums, int k) {
        //思路：
        //使用一个双向队列存储滑动窗口中的数值，且递减，确保最大元素永远在队列首部
        //每次移动滑动窗口，会新增一个nums[j+1],移除一个nums[i-1]
        if (nums.length==0||k==0)return new int[0];
        int[] res=new int[nums.length-k+1];
        Deque<Integer> deque = new LinkedList<>();
        for (int j=0,i=1-k;j<nums.length;j++,i++){
            //删除队列中的nums[i-1]
            if (i>0&&deque.peekFirst()==nums[i-1])
                deque.removeFirst();
            //使队列单调递减
            //删除队列中所有小于 nums[j]的元素，保持递减
            while(!deque.isEmpty()&&deque.peekLast()<nums[j])
                deque.removeLast();
            deque.addLast(nums[j]);
            //将每个滑动窗口的最大值加入res中
            res[j]=deque.peekFirst();

        }
        return res;
    }
}
